/**ver: 0.1, date 27-12-2007 by Marcel Hekman
 * implemented:
 * 	public: initialise, isDone, tick
 * 	private: turnLeft, turnRight, moveForward, directionHasWall, moveToNextElement, goBackwards()
 * 	protected: findStart <-- should be moved to an abstract class
 * ver: 0.2, date 03-01-2007 by Marcel Hekman
 *  bugfix: No longer searches outside the maze (still bugs left though).
 */

package mazeAssignment.solve;

import mazeAssignment.*;

/**
*
* @author: jeroen, jeroen, marcel en teun
*/
public class RightHandSolve implements Solve
{
	private static final int NORTH = 0;
	private static final int EAST = 1;
	private static final int SOUTH = 2;
	private static final int WEST = 3;
	
	protected Maze maze;
	private boolean finished;
	private int direction;
	private int posX, posY;
	
	
	@Override
	public void initialise(Maze m) throws SolveException
	{
		this.maze = m;
		finished = false;
		
		findStart();
	}

	@Override
	public boolean isDone()
	{
		return finished;
	}

	@Override
	public void tick() throws SolveException
	{
		if(finished)
			throw new SolveException("tick(): Already finished.");
		
		if(move(true))
		{
			//Mark current element as visited.
			maze.visit(posX, posY);
		}
		else
		{
			//'Dead end' so go back the way we came
			turnLeft();
			
			//There shouldn't be a wall here
			assert(! directionHasWall());
			
			//We go all the way back we came until we find an unvisited spot in one tick().
			goBackwards();
			
			//Mark current element as visited.
			maze.visit(posX, posY);
		}
	}
	
	/**
	 * Tries three walls. The wall on the right, in front and on the left.
	 * @return True if a way if found, else false.
	 * @throws SolveException 
	 */
	private boolean move(boolean forward) throws SolveException
	{
		//Try the wall on the right.
		if(! directionHasWall())
		{
			moveToNextElement(forward);
			return true;
		}
		
		//Try the wall in front.
		turnLeft();
		if(! directionHasWall())
		{
			moveToNextElement(forward);
			return true;
		}
		
		//Try the wall on the left.
		turnLeft();
		if(! directionHasWall())
		{
			moveToNextElement(forward);
			return true;
		}
		
		return false;
	}
	
	
	/**
	 * Returns true if the current directions is walled, else false.
	 * @return True if the current directions is walled, else false.
	 */
	private boolean directionHasWall()
	{
		if(direction == NORTH && posY > 0)
		{
			return maze.getNorth(posX, posY);
		}
		else if(direction == EAST && posX + 1 < maze.getSizeX())
		{
			return maze.getEast(posX, posY);
		}
		else if(direction == SOUTH && posY + 1 < maze.getSizeY())
		{
			return maze.getSouth(posX, posY);
		}
		else if(direction == WEST && posX > 0)
		{
			return maze.getWest(posX, posY);
		}
		
		//If we end up here it was at the edge of the maze and therefore a wall.
		return true;
	}
	
	/**
	 * Moves to the next element.
	 * Assumes the outer wall is always walled.
	 * @throws SolveException When the maze contains a loop.
	 */
	private void moveToNextElement(boolean forward) throws SolveException
	{
		if(direction == NORTH) {
			posY--;
		}
		else if(direction == EAST) {
			posX++;
		}
		else if(direction == SOUTH) {
			posY++;
		}
		else {
			posX--;
		}
		
		//Check if we have reached the end
		if(maze.getSolveState(posX, posY) == Maze.SOLVE_END)
		{
			this.finished = true;
			return;
		}
		else if(forward && maze.isVisited(posX, posY))
		{
			throw new SolveException("RightHandSolve: moveToNextElement(): Maze contains a loop! (moving forward)");
		}
		else if(!forward && maze.getSolveState(posX, posY) == Maze.SOLVE_INVALID)
		{
			throw new SolveException("RightHandSolve: moveToNextElement(): Maze contains a loop! (moving backward)");
		}
		
		//Make sure the wall on the right is checked first at the next tick().
		turnRight();
	}
	
	/**
	 * Used when we end up a tunnel that turns out to be a dead end.
	 * @throws SolveException 
	 */
	private void goBackwards() throws SolveException
	{
		int previousX = posX;
		int previousY = posY;
		
		while(maze.isVisited(posX, posY))
		{
			maze.markAsInvalid(previousX, previousY);
			previousX = posX;
			previousY = posY;
			
			//Move further back
			if(! move(false))
				throw new SolveException("RightHandSolve: goBackwards(): Unable to find an unvisited spot, maze invalid?");
		}
	}
	
	private void turnLeft()
	{
		//orientation = (orientation + 3) % 4;
		direction = (direction + 3) & 3;			//Same operation but apparently a bit faster
	}
	
	private void turnRight()
	{
		//orientation = (orientation + 1) % 4;
		direction = (direction + 1) & 3;			//Same operation but apparently a bit faster
	}
	
	/**
	 * Finds the start item in the maze
	 * Assumes the start point is not in the center of the maze.
	 * @throws SolveException If no start element is found.
	 */
	private void findStart() throws SolveException
	{
		int xSize = maze.getSizeX();
		int ySize = maze.getSizeY();
		
		//Search the entire maze
		for(int x = 0; x < xSize; x++)
		{
			for(int y = 0; y < ySize; y++)
			{
				if(maze.getSolveState(x, y) == Maze.SOLVE_START)
				{
					this.posX = x;
					this.posY = y;
					
					if(!maze.getNorth(x, y))
						direction = NORTH;

					if(!maze.getEast(x, y))
						direction = EAST;

					if(!maze.getSouth(x, y))
						direction = SOUTH;

					if(!maze.getWest(x, y))
						direction = WEST;
					return;
				}
			}
		}
		
		throw new SolveException("findStart: Unable to find start element.");
	}
}
